package com.leetcode.algorithm.y22.m08.w4;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 658. 找到 K 个最接近的元素
 * 
 * https://leetcode.cn/problems/find-k-closest-elements/
 * 
 * @author jie.deng
 *
 */
class Question0658Solution02 {

	public List<Integer> findClosestElements(int[] arr, int k, int x) {
		int len = arr.length;
		if (k >= len) {
			return IntStream.of(arr).boxed().collect(Collectors.toList());
		}
		if (arr[0] >= x) {
			return IntStream.of(arr).limit(k).boxed().collect(Collectors.toList());
		} else if (arr[len - 1] <= x) {
			return IntStream.of(arr).skip(len - k).boxed().collect(Collectors.toList());
		}

		// 1.查找分割点
		int right = searchInsertIdx(arr, x);
		int left = right - 1;
		int cnt = k;
		// 2.从分割点往两边拓展
		while (cnt > 0 && left >= 0) {
			if (x - arr[left] > arr[right] - x) {
				right++;
				if (right == len) {
					left = len - k - 1;
					break;
				}
			} else {
				left--;
			}
			cnt--;
		}
		return IntStream.of(arr).skip(left + 1).limit(k).boxed().collect(Collectors.toList());
	}

	private int searchInsertIdx(int[] arr, int target) {
		int left = 0;
		int right = arr.length - 1;
		// [left, right]
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (arr[mid] >= target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return right;
	}

}